package gsw.tool.datastructure.tree;

import java.util.NoSuchElementException;

import gsw.tool.common.ToolShow;

/**
 * 二叉查找树(二叉排序树)或者是一棵空树，或者是具有下列性质的二叉树：
 * 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
 * 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
 * 它的左、右子树也分别为二叉排序树。
 */
public class TreeBinarySearch<E extends Comparable> extends TreeBinary<E> {

    public static void test() {
        TreeBinarySearch<Integer> tree = new TreeBinarySearch<Integer>();
        tree.createData();

        tree.recursionPre();
        ToolShow.log("-------------------------------------");

        Node<Integer> query = tree.get(2);
        Integer result = query == null ? null : query.data;
        ToolShow.log("query:" + result);

        tree.remove(10);
        tree.recursionPre();
        ToolShow.log("-------------------------------------");
    }

    /**
     * 添加元素
     *
     * @param data 当前元素
     */
    public void put(E data) {
        Node<E> now = new Node<E>(data);
        if (root == null) {
            root = now;
            return;
        }

        Node<E> parent = root;
        while (parent != null) {
            //小于当前节点，就与左子树比较
            if (data.compareTo(parent.data) < 0) {
                //如果左子节点为空，那就放到左子节点
                if (parent.left == null) {
                    parent.left = now;
                    now.parent = parent;
                    return;
                    //如果左子节点不为空，那就继续比较
                } else {
                    parent = parent.left;
                }
                //大于当前节点，就放与右子树比较
            } else if (data.compareTo(parent.data) > 0) {
                //如果右子节点为空，那就放到右子节点
                if (parent.right == null) {
                    parent.right = now;
                    now.parent = parent;
                    return;
                    //如果右子节点不为空，那就继续比较
                } else {
                    parent = parent.right;
                }
            } else {
                return;
            }
        }

    }

    /**
     * 查找元素
     *
     * @param data 当前元素
     * @return 查找结果
     */
    public Node<E> get(E data) {
        if (root == null) {
            return null;
        }
        Node<E> now = root;
        while (now != null) {
            //小于当前节点，就与左子树比较
            if (data.compareTo(now.data) < 0) {
                now = now.left;
                //大于当前节点，就放与右子树比较
            } else if (data.compareTo(now.data) > 0) {
                now = now.right;
                //等于当前节点，就直接返回当前节点
            } else {
                return now;
            }
        }
        return null;
    }

    /**
     * 删除元素
     * 1.若p有右子树，找到其右子树的最左子节点r，用r来替代p;
     * 2.若p有左子树，没有右子树，找到其左子树的最右子节点l，用l来替代p;
     * 3.若p是叶子节点，则直接删除
     *
     * @param data
     * @return
     */
public Node<E> remove(E data) {
    Node<E> p = get(data);
    if (p == null) {
        throw new NoSuchElementException();
    }
    //p的右子树的最左子节点r
    Node<E> r = nodeLeft(p.right);
    //p的左子树的最右子节点l
    Node<E> l = nodeRight(p.left);
    if (r != null) {
        p.data = r.data;
        //如果p的右子结点有左节点
        if (r != p.right) {
            r.parent.left = r.right;
        } else {
            p.right = p.right.right;
        }
        r.left = r.right = r.parent = null;
    } else if (l != null) {
        p.data = l.data;
        //如果p的左子结点有右节点
        if (l != p.left) {
            l.parent.right = l.left;
        } else {
            p.left = p.left.left;
        }
        l.left = l.right = l.parent = null;

        //如果p是叶子节点
    } else {
        if (p.parent == null) {
            root = null;
        } else if (p.parent.left == p) {
            p.parent.left = null;
        } else {
            p.parent.right = null;
        }
        p.parent = null;
    }
    return p;
}

    /**
     * 获取当前节点的最左子节点
     *
     * @param data
     * @return
     */
    public Node<E> nodeLeft(Node<E> data) {
        if (data == null) {
            return null;
        }
        Node<E> now = data;
        while (now.left != null) {
            now = now.left;
        }
        return now;
    }

    /**
     * 获取当前节点的最右子节点
     *
     * @param data
     * @return
     */
    public Node<E> nodeRight(Node<E> data) {
        if (data == null) {
            return null;
        }
        Node<E> now = data;
        while (now.right != null) {
            now = now.right;
        }
        return now;
    }

    /**
     * 创建数据
     */
    @Override
    public void createData() {
        Integer[] list = new Integer[]{10, 1, 2, 44, 5, 7, 9};
        for (Integer i : list) {
            put((E) i);
        }
    }

}
